class Solution {
public:
    string reorganizeString(string s) {
        unordered_map<char, int> hash;
        int MaxValue = 0, MaxCount = 0;
        for (auto x : s)
        {
            if (MaxCount < ++hash[x])
                MaxCount = hash[x], MaxValue = x;
        }

        int n = s.size();
        if (MaxCount > (n + 1) / 2) return "";

        string ret(n, ' ');
        int i = 0;
        while (MaxCount--)
        {
            ret[i] = MaxValue;
            i += 2;
        }

        hash.erase(MaxValue);
        for (auto x : hash)
        {
            while (x.second--)
            {
                if (i >= n) i = 1;

                ret[i] = x.first;
                i += 2;
            }
        }

        return ret;
    }
};